Cours 2.11.1 du Mastère de Recherches en Informatique <br />Algorithmes avancés - Nicolas Schabanel <br /> <br />Cours n°1 - Partie B/C <br />Introduction aux algorithmes d'approximation <br />• NP-complétude, PCP et Inapproximabilité <br />• Définitions: Problèmes d'optimisation et approximation <br />• Inapproximabilité du TSP non-métrique <br />• Une 2-approximation pour le TSP métrique <br />• Une 3/2-approximation pour le TSP métrique <br /> <br />TD n°1 <br />• Dérandomisation par la méthode de l'espérance conditionnelle appliquée à Max-Cut <br />• Une O(√n)-approximation pour le coloriage de graphes 3-coloriables
